package Array;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: Array
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-19  23:03
 * @Description: TODO
 * @Version: 1.0
 */
public class 加油站134 {

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int totalSum = 0;
        int index = 0;
        for (int i = 0; i < gas.length; i++) {
            // 计算每一次的能够留存多少油料
            curSum += gas[i] - cost[i];
            // 表示所有的剩余的油料都相加
            totalSum += curSum;
            // 如果当前是《0 那就需要重下一个位置开始，并设置currSum 为0 重新计算
            if (curSum < 0) {
                index = (i + 1) % gas.length;
                curSum = 0;
            }
        }
        if (totalSum < 0) {
            return -1;
        }
        return index;
    }

    public int canCompleteCircuit2(int[] gas, int[] cost) {
        int n = gas.length;
        // 表示从第0个位置开始遍历
        int i = 0;
        while (i < n) {
            int sumOfGas = 0, sumOfCost = 0;
            int cnt = 0;
            while (cnt < n) {
                int j = (i + cnt) % n;
                sumOfGas += gas[j];
                sumOfCost += cost[j];
                // 如果花的是大于得到的那就break
                if (sumOfCost > sumOfGas) {
                    break;
                }
                cnt++;
            }
            if (cnt == n) {
                return i;
            } else {
                i = i + cnt + 1;
            }
        }
        return -1;
    }
}
